package leetcode_1100;

/**
 *@author 周杨 
 *MinimumScoreTriangulationOfPolygon_1039_ 给一个数组 顺时针表示一个多边形的每个顶点的值 将其分割成不相交的n-2个三角形 问最终所有三角形顶点和最小值是多少
 *describe:动态规划 利用局部最优解
 *2019年5月18日 下午13:37
 */
public class MinimumScoreTriangulationOfPolygon_1039_ {
	public int minScoreTriangulation(int[] A) {
        return this.help(A,0,A.length-1,new int[A.length][A.length]);
    }
	
	private int help(int[] A,int left,int right,int[][]dp) {
		if(dp[left][right] != 0) return dp[left][right];
		if(right-left < 2) return 0;
		if(right-left == 2) return A[left]*A[left+1]*A[right];
		int min = Integer.MAX_VALUE;
		for(int i=left+1;i<right;++i) {//以left和right为边 找出一个三角形 然后把这个多边形划分成三个多边形
			int now = A[left]*A[right]*A[i];
			now += help(A,left,i,dp);
			now += help(A,i,right,dp);
			min = Math.min(min, now);
		}
		dp[left][right] = min;
		return min;
	}
}
